package com.cat.DataStructure04;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/prefix-and-suffix-search/
 * @create 2025/11/27 16:20
 * @since JDK17
 */
public class WordFilter {
    static int N = ((int) 1e5), cnt1, cnt2;
    static int[][] tree1 = new int[N][26], tree2 = new int[N][26];
    static List<Integer>[] pass1 = new List[N], pass2 = new List[N];

    static {
        Arrays.setAll(pass1, x -> new ArrayList<>());
        Arrays.setAll(pass2, x -> new ArrayList<>());
    }

    static void clear() {
        for (int i = 1; i <= cnt1; i++) {
            Arrays.fill(tree1[i], 0);
            pass1[i].clear();
        }
        for (int i = 1; i <= cnt2; i++) {
            Arrays.fill(tree2[i], 0);
            pass2[i].clear();
        }
    }

    static void insert(String word, int idx) {
        int cur1 = 1, cur2 = 1;
        for (int i = 0, j = word.length() - 1, p1, p2; i < word.length(); i++, j--) {
            p1 = word.charAt(i) - 'a';
            p2 = word.charAt(j) - 'a';
            if (tree1[cur1][p1] == 0) {
                tree1[cur1][p1] = ++cnt1;
            }
            if (tree2[cur2][p2] == 0) {
                tree2[cur2][p2] = ++cnt2;
            }
            cur1 = tree1[cur1][p1];
            cur2 = tree2[cur2][p2];
            pass1[cur1].add(idx);
            pass2[cur2].add(idx);
        }
    }

    static int search(String prefix, String suffix) {
        int cur = 1, i, path;
        for (i = 0; i < prefix.length(); i++) {
            path = prefix.charAt(i) - 'a';
            if (tree1[cur][path] == 0) {
                return -1;
            }
            cur = tree1[cur][path];
        }
        var l1 = pass1[cur];
        cur = 1;
        for (i = suffix.length()- 1; i >= 0; i--) {
            path = suffix.charAt(i) - 'a';
            if (tree2[cur][path] == 0) {
                return -1;
            }
            cur = tree2[cur][path];
        }
        var s1 = new HashSet<Integer>(pass2[cur]);
        for (i = l1.size() - 1; i >= 0; i--) {
            if (s1.contains(l1.get(i))) {
                return l1.get(i);
            }
        }
        return -1;
    }

    public WordFilter(String[] words) {
        clear();
        cnt1 = cnt2 = 1;
        for (int i = 0; i < words.length; i++) {    // 生成前缀树
            insert(words[i], i);
        }
    }

    public int f(String pref, String suff) {
        return search(pref, suff);
    }
}
